package leetcode.tree;

public class Lc720 {



    public String longestWord(String[] words) {

        Trie trie = new Trie();
        for (int i = 0; i < words.length; i++) {
            trie.insert(words[i]);
        }
        String ans = "";
        for (int i = 0; i < words.length; i++) {
            if (trie.search(words[i]))
                ans = max(ans, words[i]);
        }
        return ans;
    }

    private String max(String s1, String s2) {
        if (s1.length() == s2.length()) {
            if (s1.compareTo(s2) > 0) return s2;
            return s1;
        }
        if (s1.length() > s2.length()) return s1;
        return s2;
    }

    class Trie {

        public Trie[] children;
        public boolean isEnd;

        public Trie() {
            this.children = new Trie[26];
            this.isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int idx = ch - 'a';
                if (node.children[idx] == null)
                    node.children[idx] = new Trie();
                node = node.children[idx];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int idx = ch - 'a';
                if (!node.children[idx].isEnd) return false;
                node = node.children[idx];
            }
            return true;
        }
    }

    public static void main(String[] args) {
        String s1 = "abc";
        String s2 = "ddd";
        System.out.println(s1.compareTo(s2));
    }
}
